package com.tgy.skiplist;

import java.util.Comparator;
import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-11-19 13:59
 *
 * 跳表是一个有序链表，
 *
 */
public class SkipList<K,V> {

    /**
     * 最大层数
     */
    private final static int MAX_LEVEL = 32;

    /**
     * 元素个数
     */
    private int size;

    /**
     * first node
     */
    private Node<K,V> first;

    private static final double P = 0.25;


    /**
     * 当前层数
     */
    private int level;

    private Comparator<K> comparator;

    private static class Node<K,V> {

        K key;
        V val;


        Node<K,V>[] nodes;

        public Node() {

            this(null,null,MAX_LEVEL);
        }

        public Node(K key, V val, int level) {

            this.key = key;
            this.val = val;
            nodes = new Node[level];
        }

        @Override
        public String toString() {
            return "k-" + key + ":" + "v-" + val;
        }
    }

    public SkipList() {

        this(null);
    }

    public SkipList(Comparator<K> comparator) {
        this.comparator = comparator;
        first = new Node<>();
    }

    /**
     * 判断跳表是否为空
     * @return
     */
    public boolean isEmpty() {

        return size == 0;
    }

    /**
     * 通过key 获取对应的val
     * @param key
     * @return
     */
    public V get(K key) {

        checkKey(key);

        Node<K, V> node = findNode(key,0);

        if (Objects.nonNull(node) && node != first && cmp(key,node.key) == 0) {

            return node.val;
        }

        return null;
    }

    /**
     * 把key
     * @param key
     * @param val
     * @return
     */
    public V put(K key,V val) {

        checkKey(key);

        Node<K, V> node = this.first;

        int cmpResult = 0;

        Node<K,V>[] preNodes = new Node[level];

        for (int i = level - 1; i >= 0; i--) {

            Node<K, V> nextNode = node.nodes[i];
            while (Objects.nonNull(nextNode) && (cmpResult = cmp(key,nextNode.key)) > 0) {

                node = nextNode;
                nextNode = node.nodes[i];
            }


            if (cmpResult == 0) {

                V oldVal = nextNode.val;
                nextNode.val = val;
                return oldVal;
            }

            // 这里包含 nextNode = null 和 cmpResult < 0
            preNodes[i] = node;
        }

        int nodeLevel = nodeLevel();

        Node<K, V> newNode = new Node<>(key, val, nodeLevel);

        for (int i = nodeLevel - 1; i >= 0; i--) {

            if (i >= level) {

                first.nodes[i] = newNode;
            }else {

                Node<K, V> nextNode = preNodes[i].nodes[i];
                preNodes[i].nodes[i] = newNode;
                newNode.nodes[i] = nextNode;
            }
        }

        // 更新size
        size++;

        // 更新level
        if (nodeLevel > level) {

            level = nodeLevel;
        }

        return null;
    }

    /**
     * 把key
     * @param key
     * @return
     */
//    public V put01(K key,V val) {
//
//        checkKey(key);
//
//        if (level == 0) {
//
//            Node<K, V> newNode = new Node<>(key, val);
//            first.nodes[0] = newNode;
//            level++;
//            size++;
//            return null;
//        }
//
//        Node<K, V> node = findNode(key,0);
//
//        // 如果存在，替换之前的
//        if (first != node && cmp(node.key,key) == 0) {
//
//            V oldVal = node.val;
//            node.val= val;
//            return oldVal;
//        }
//
//        size++;
//        Node<K, V> newNode = new Node<>(key, val);
//
//        Node<K, V> oldNextNode = node.nodes[0];
//        node.nodes[0] = newNode;
//        newNode.nodes[0] = oldNextNode;
//
//        if (first == node) {
//
//            return null;
//        }
//
//        int nodeLevel = nodeLevel();
//
//        for (int i = 1; i < nodeLevel ; i++) {
//
//            Node<K, V> levelBeforeNode = findNode(key, i);
//            Node<K, V> nextNode = levelBeforeNode.nodes[i];
//            levelBeforeNode.nodes[i] = newNode;
//            newNode.nodes[i] = nextNode;
//        }
//
//        if (nodeLevel > level) {
//
//            level = nodeLevel;
//        }
//
//        return null;
//    }

    public V remove(K key) {

        checkKey(key);

        Node<K,V> node = first;
        Node<K,V>[] preNodes = new Node[level];

        int cmpResult = -1;
        boolean isExist = false;
        for (int i = level - 1; i >= 0; i--) {

            Node<K,V> nextNode = node.nodes[i];
            while (Objects.nonNull(nextNode) && (cmpResult = cmp(key,nextNode.key)) > 0) {

                node = nextNode;
                nextNode = node.nodes[i];
            }

            if (cmpResult == 0) {

                isExist = true;
                preNodes[i] = node;
            }

        }

        // 不存在key
        if (!isExist) {

            return null;
        }

        Node<K,V> retNode = null;

        for (int i = level - 1; i >= 0; i--) {

            Node<K, V> preNode = preNodes[i];

            if (Objects.nonNull(preNode)) {

                retNode = preNode.nodes[i];
                preNode.nodes[i] = preNode.nodes[i].nodes[i];
            }
        }

        int beforeLevel = level;
        for (int i = level - 1; i >= 0; i--) {

            if (Objects.isNull(first.nodes[i])) {

                beforeLevel--;
            }else {

                break;
            }
        }

        if (beforeLevel != level) {

            level = beforeLevel;
        }
        size--;
        return retNode.val;
    }

    public void printSkipList() {

        if (level == 0) {
            return;
        }

        System.out.println("size:" + size);
        int printMax = 100;
        for (int i = level - 1; i >= 0; i--) {

            Node<K, V> node = this.first.nodes[i];
            System.out.print((i + 1) + "==== ");
            int count = 0;
            while (Objects.nonNull(node)) {

                if (count < printMax) {

                    System.out.print(node.toString() + "   ");
                }
                node = node.nodes[i];
                count++;
            }

            System.out.println();
        }

    }

    private Node<K,V> findNode(K key,int lv) {

        Node<K, V> curNode = first, node;
        for (int i = level - 1; i >= lv; i--) {

            node = curNode.nodes[i];
            int cpmResult = 0;
            while (Objects.nonNull(node) && (cpmResult = cmp(key,node.key)) > 0) {

                curNode = node;
                node = curNode.nodes[i];
            }

            if (Objects.isNull(node)) {

                continue;
            }

            if (cpmResult == 0) {

                return node;
            }

        }

        return curNode;
    }

    private int cmp(K k1, K k2) {

        if (Objects.nonNull(comparator)) {

            return comparator.compare(k1,k2);
        }
        return ((Comparable<K>)k1).compareTo(k2);
    }

    private int nodeLevel() {

        int randomLevel = 1;


        while (Math.random() <= P) {

            randomLevel++;
        }

        return randomLevel > MAX_LEVEL ? MAX_LEVEL:randomLevel;
    }

    private void checkKey(K key) {

        if (Objects.isNull(key)) {

            throw new IllegalArgumentException("key not null");
        }

    }
}
